package leetcode.N401_N500;

import leetcode.comm.ListNode;


public class N445 {

    public static void main(String[] args) {
        ListNode l1 = ListNode.generate(1,2,3,4,5);
        ListNode l2 = ListNode.generate(2,3,4,5);

        System.out.println(addTwoNumbers(l1, l2));


    }

    static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode l01 = l1;
        ListNode l02 = l2;
        // 对其两个链表
        while (l01 != null || l02 != null) {
            if (l01 == null) {
                // l2比l1长 则在l1头部补位
                l1 = link(0, l1);
                l02 = l02.next;
            } else if (l02 == null) {
                // l1比l2长 则在l2头部补位
                l2 = link(0, l2);
                l01 = l01.next;
            } else {
                l01 = l01.next;
                l02 = l02.next;
            }
        }

        // 链表相加 保留数字
        ListNode sum = new ListNode(l1.val + l2.val);
        for (ListNode n1 = l1.next, n2 = l2.next; n1 != null; n1 = n1.next, n2 = n2.next) {
            sum = link(n1.val + n2.val, sum);
        }

        // 遍历和 进行进位和反转操作
        int carry;
        ListNode result;
        if (sum.val >= 10) {
            result = new ListNode(sum.val - 10);
            carry = 1;
        } else {
            result = new ListNode(sum.val);
            carry = 0;
        }

        for (ListNode node = sum.next; node != null; node = node.next) {
            int val = node.val + carry;
            if (val >= 10) {
                carry = 1;
                result = link(val - 10, result);
            } else {
                carry = 0;
                result = link(val, result);
            }
        }

        // 有进位 则补最高位
        if (carry == 1) {
            result = link(1, result);
        }
        return result;
    }

    private static ListNode link(int val, ListNode next) {
        ListNode temp = new ListNode(val);
        temp.next = next;
        return temp;
    }
}
